package com.code.leetcode._202507;

import java.util.Queue;

// 50 pow(x,n)
public class MyPow {
    /**
     * 实现pow(x,n)，即计算x的整数n次幂函数
     * 示例1：输入：x=2.00000,n=10
     * 输出：1024.0000
     * 示例2：输入：x=2.10000,n=3
     * 输出：9.26100
     * 示例3：输入：x=2.0000,n=-1
     * 输出：0.25000
     * 解释：2的-2次方= 1/2^2= 1/4=0.25
     **/
    public static void main(String[] args) {
        MyPow m = new MyPow();
        System.out.println(m.myPow1(2.00, 10));
    }

    /**
     * 快速幂+递归
     * 快速幂算法 的本质是分治计算，举个例子，如果我们要计算x的64次方，我们可以按照：
     * x->x^2->x^4->x^8->x^16->x^32->x^64
     * 的顺序，从x开始，每次直接把上一次的结果进行平方，计算6次就可以得到x^64的值，而不需要对x乘63次x
     * 再举一个例子，如果我们要计算x^77，我们可以按照x->x^2->x^4->x^9->x^19->x^38->x^77
     * 的顺序，在x->x^2,x^2->x^4,x^19->x^38这些步骤中，我们直接把上一次的结果进行平方，而在
     * x^4->x^9，x^9->x^19，x^38->x^77这些步骤中，我们把上一次的结果进行评分后，还要额外乘一个x
     * 直接从左到右进行推导看上去困难，因为在每一步中，我们不直到在将上一次的结果平方之后，还需不需要额外乘x，
     * 但如此我们从右往左看，分治的思想就十分明显了：
     * 1、当我们要计算x^n时，我们可以先递归地计算处y=x^[n/2]，其中⌊a⌋表示对a进行向下取整
     * 2、根据递归计算地结果，如果n为偶数，那么x^n=y^2，如果n为奇数，那么x^n=y^2*x
     * 3、递归地边界为n=0，任意数地0次方均为1
     * 由于每次递归都会使得指数集减少一半，因此递归地层数为O(log n)，算法可以在很快地时间内得到结果。
     **/
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    /**
     * 快速幂+迭代
     * 由于递归需要使用额外地栈空间，我们试着将递归转写为迭代。在方法一中，我们也提到过，从左到右进行推导是不容易地，
     * 因为我们不直到是否需要额外乘x，但我们不妨找一些规律，看看哪些地方额外乘了x，并且他们对答案产生了什么影响。
     * 我们还是以x^77作为例子：x->x^2->x^4->+x^9->+x^19->x^38->+x^77
     * 并且把需要额外乘x地步骤打上了+标记。我们可以发现：
     * 1、x^38->+x^77 中额外乘地x在x^77中贡献了x
     * 2、x^9->+x^19 中额外乘地x在之后被平方了2次，因此在x^77中贡献了x^2^2=x^4
     * 3、x^4->+x^9 中额外乘地x在之后被平方了3次，因此在x^77中贡献了x^2^3=x^8
     * 4、最初地x在之后被平方了6次，因此在x^77中贡献了x^2^6=x^64
     * 我们把这些贡献相乘，x*x^4*x^8*x^64恰好等于x^77。而这些贡献地指数部分又是什么呢？他们都是2地幂次，
     * 这是因为这个额外乘地x在之后都会被平方若干次。而这些指数1，4，8和64，恰好就对应了77地二进制表示(10011010)2
     * 中地每个1!因此我们借助整数地二进制拆分，就可以得到迭代计算的方法，一般地，如果整数n的二进制拆分为
     * n=2^i0+2^i1+...+2^ik  那么x^n=x^2^i0*x^2^i1*...*x^2^ik
     * 这样以来，我们从x开始不断地进行平方，得到x^2,x^4,x^8,x^16,...,如果n地第k个(从右往左，从0开始计数)二进制
     * 位为1，那么我们就将对应的贡献x^2^k计入答案
     **/
    public double myPow1(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul1(x, N) : 1.0 / quickMul1(x, -N);
    }

    public double quickMul1(double x, long N) {
        double ans = 1.0;
        double x_contribute = x;
        while (N > 0) {
            if (N % 2 == 1) {
                ans *= x_contribute;
            }
            x_contribute *= x_contribute;
            N /= 2;
        }
        return ans;
    }
}
